In recent years, the computer and electronics industries have experienced a trend toward adopting network-like architectures (commonly referred to as I/O “fabrics”) for performing input/output functions traditionally performed by buses and bus-like structures. These include storage-area network (SAN) architectures such as INFINIBAND®. As in the case of wide-area networks, such as the Internet, many of these intra-system fabrics transmit data in the form of packets, which are routed through fabric-attached components referred to as “switches.” This routing of packets is commonly referred to as “packet switching.”
In some packet switching fabrics, a priority may be assigned to packets to facilitate routing through the fabric. The RAPIDIO™ protocol, an industry interconnection standard for embedded systems, is an example of one such packet switching protocol. In the RAPIDIO™ protocol, higher-priority packets are intended to have shorter transmission latencies than lower priority packets. Thus, higher-priority packets may pass lower-priority packets in the fabric.
A packet switch is implemented with a number of ports. Each port may act as an input port (accepting packets from outside the switch), or as an output port (transmitting packets to destinations outside of the switch), or, most commonly, a port may act as both an input and an output port.
If a switch has a packet queue on an input port, higher-priority packets that arrive after lower-priority ones can be blocked in the input queue, due to the inability of the switch to route the lower-priority packets that are ahead in the input queue. Since higher-priority packets are intended to have shorter transmission latencies than their lower-priority counterparts, this blocking is clearly undesirable.
Existing solutions to this problem include eliminating the input queue and equipping the port with multiple parallel input queues (one for each priority). These existing solutions, however, suffer from a number of drawbacks. In particular, these existing solutions tend to be expensive in terms of hardware requirements or implementation complexity.
If a switch has only output queuing (and no input queue), extensive buffering of packets is required. In particular, one output queue per priority per input port is needed. This scheme becomes unacceptably expensive as the number of ports in the switch grows.
Input ports that have separate input queues for each priority add both complexity and cost to the implementation. Moreover, such a design may also lower overall through-put by making less efficient use of memory buffers, as each individual input queue is only allowed to hold packets of a particular priority.
Thus, what is needed is a simple, inexpensive queuing system in which blocking of high-priority packets is reduced. The present invention provides a solution to this and other problems, and offers other advantages over previous solutions.